https://leetcode.cn/problems/product-of-array-except-self/description/
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> f(n+1),g(n+1),ret(n);
        f[0]=g[n-1]=1;
        for(int i=1;i<n;i++)
            f[i]=f[i-1]*nums[i-1];
        for(int j=n-2;j>=0;j--)
            g[j]=g[j+1]*nums[j+1];

        for(int i=0;i<n;i++)
            ret[i]=f[i]*g[i];
        return ret;
    }
};